//希尔排序类似于插入排序，就是多了个步长

let gaps = [5,3,1] //步长，经验主义

function shellSort(arr){
    for(let index = 0; index < gaps.length; index++){
        for(let i = gaps[index]; i < arr.length; i++){
            let temp = arr[i]
            let j = i
            while(j >= gaps[index] && arr[j - gaps[index]] >temp){
                arr[j] = arr[j - gaps[index]]
                j-= gaps[index]
            }
            arr[j] = temp
        }
    }
    return arr
}

let arr = [1,5,6,8,2,4,3,9,77,21,45,0,46,31]
shellSort(arr)